# -*- coding: utf-8 -*-

"""剑指 Offer II 001. 整数除法
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：
    整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
    假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1"""

class Solution():
    """整数地板除法，可以利用减法解决，明确解题方向，具体算法就看怎么减的问题了， 我们一步步来
    1.如 15/2，挨个减计数没问题，但是碰到 2147483647/2 这类问题呢？所以挨个减的方案不适合
    2.这种类似用步长来丈量终点的问题，可以想到经典的二分法思想，倍增翻倍。不由地想到关系型数据库中生成连续数字的工具表nums，也是利用倍增来快速达到
    3.但是在某次翻倍之后，超过终点的时候，理想的二分是想找到最后一次翻倍的中点位置，但是这就需要利用求中点的除二运算，与题目要求不符
    4.一番思量之后，决定分步骤，如果再翻一次，就超过终点，则从此点截断，将当前用的步数加到总步数中；并初始化步数，将后面的长度再从第一步开始计数......循环往复，直到剩余长度小于步长，结束
    5.将边界条件进行特殊处理，如除数为1, 被除数小于除数等，可以直接给结果的不再计算
    
    最终提交结果：
    992 / 992 个通过测试用例
    状态：通过
    执行用时: 32 ms
    内存消耗: 15 MB"""
    def divide(self, a: int, b: int):
        if b == 0:
            raise ZeroDivisionError(b)
        
        if a == 0:
            return 0
        
        a, b, same = self.abs(a), self.abs(b), self.issame(a, b)
        
        if b == 1:
            quo = a
            if not same:
                quo = 0-a
            return self.over_filter(quo)

        if a < b:
            return 0

        return self.floor_divide(a, b, same)
    
    @staticmethod
    def abs(x):
        if x < 0:
            return 0-x
        else:
            return x

    @staticmethod
    def issame(a, b):
        if (a > 0 and b < 0) or (a < 0 and b > 0):
            return False
        else:
            return True
    
    @staticmethod
    def over_filter(quo):
        if quo > 2147483647 or quo < -2147483648:
            return 2147483647
        else:
            return quo
    
    def floor_divide(self, a, b, sign):
        quotient, count, top, total = 0, 1, a, b
        while True:
            if top < total:
                break
            
            double = total + total
            if double > top:
                quotient += count
                top -= total
                count, total = 1, b
            else:
                total = double
                count += count
        
        if not sign:
            quotient = 0-quotient
        
        return self.over_filter(quotient)


if __name__ == '__main__':
    def test(a, b):
        so = Solution()
        quo = so.divide(a, b)
        print('a:%s / b:%s = quo:%s' % (a, b, quo))

    # test(1, 0)
    test(0, 3)
    test(3, 7)
    test(16, 3)
    test(16, 2)
    test(-1, 8)
    test(9, -3)
    test(2**31-1, 2)
    test(-2**31, -1)
